package com.Offer;

/*
    面试题49：丑数
    题目描述：求从小到大的第 N 个丑数。丑数是只包含因子 2、3 和 5 的数，习惯 上我们把 1 当做是第一个丑数。
 */
public class demo49 {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(getUglyNumber(n));
    }

    public static int getUglyNumber(int n){
        if(n <=0){
            return 0;
        }
        int[] arr = new int[n];
        int multiply2 = 0;
        int multiply3 = 0;
        int multiply5 = 0;
        arr[0] = 1;

        for(int i =1;i<n;i++){
            int min = Math.min(arr[multiply2]*2,Math.min(arr[multiply3]*3,arr[multiply5]*5));
            arr[i] = min;
            if(arr[multiply2]*2 == min){
                multiply2++;
            }
            if(arr[multiply3]*3 == min){
                multiply3++;
            }
            if(arr[multiply5]*5 == min){
                multiply5++;
            }
        }
        return arr[n-1];
    }
}
